package everydayone.lengthoflis;
/**
 * @Date 2020/03/14
 * @author 王光浩
 * @Thinking 使用暴力法。每次查找到某个元素，则从数组的头部开始寻找所有比该元素小的最长子序列长度。（动态规划）
 * @Analysis 时间复杂度O（n^2），空间复杂度O（n）
 */
public class MyMethodOne {
	 public int lengthOfLIS(int[] nums) {
		 if(nums.length==1)return 1;
		 int maxLength=0;
		 int[] length=new int[nums.length];
		 //外层循环遍历整个数组，内层循环查找最大值比当前元素小的最长子序列长度
		 for(int i=0;i<nums.length;i++) {
			 length[i]=1;
			 for(int j=0;j<i;j++)
				 if(nums[j]<nums[i]) {
					 length[i]=((length[j]+1)>length[i])?(length[j]+1):length[i];
				 }
			 maxLength=(length[i]>maxLength)?length[i]:maxLength;
		 }
		 return maxLength;
	  }
}
